home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 1: Comms & Networking / Almathera Ten on Ten - Disc 1: Comms & Networking.iso / generalinfo / internetstandards / rfc / 1000-1299 / rfc1245.ps < prev    next >
Text File  |  1991-08-07  |  62KB  |  947 lines
  1. %!
  2. %%BoundingBox: (atend)
  3. %%Pages: (atend)
  4. %%DocumentFonts: (atend)
  5. %%EndComments
  6. %
  7. % FrameMaker PostScript Prolog 2.0, for use with FrameMaker 2.0
  8. % Copyright (c) 1986,87,89 by Frame Technology, Inc.  All rights reserved.
  9. %
  10. % Known Problems:
  11. %    Due to bugs in Transcript, the 'PS-Adobe-' is omitted from line 1
  12. /FMversion (2.0) def 
  13. % Set up Color vs. Black-and-White
  14.     /FMPrintInColor systemdict /colorimage known def
  15. % Uncomment this line to force b&w on color printer
  16. %   /FMPrintInColor false def
  17. /FrameDict 190 dict def 
  18. systemdict /errordict known not {/errordict 10 dict def
  19.         errordict /rangecheck {stop} put} if
  20. % The readline in 23.0 doesn't recognize cr's as nl's on AppleTalk
  21. FrameDict /tmprangecheck errordict /rangecheck get put 
  22. errordict /rangecheck {FrameDict /bug true put} put 
  23. FrameDict /bug false put 
  24. mark 
  25. % Some PS machines read past the CR, so keep the following 3 lines together!
  26. currentfile 5 string readline
  27. 00
  28. 0000000000
  29. cleartomark 
  30. errordict /rangecheck FrameDict /tmprangecheck get put 
  31. FrameDict /bug get { 
  32.     /readline {
  33.         /gstring exch def
  34.         /gfile exch def
  35.         /gindex 0 def
  36.         {
  37.             gfile read pop 
  38.             dup 10 eq {exit} if 
  39.             dup 13 eq {exit} if 
  40.             gstring exch gindex exch put 
  41.             /gindex gindex 1 add def 
  42.         } loop
  43.         pop 
  44.         gstring 0 gindex getinterval true 
  45.         } def
  46.     } if
  47. /FMVERSION {
  48.     FMversion ne {
  49.         /Times-Roman findfont 18 scalefont setfont
  50.         100 100 moveto
  51.         (FrameMaker version does not match postscript_prolog!)
  52.         dup =
  53.         show showpage
  54.         } if
  55.     } def 
  56. /FMLOCAL {
  57.     FrameDict begin
  58.     0 def 
  59.     end 
  60.     } def 
  61.     /gstring FMLOCAL
  62.     /gfile FMLOCAL
  63.     /gindex FMLOCAL
  64.     /orgxfer FMLOCAL
  65.     /orgproc FMLOCAL
  66.     /organgle FMLOCAL
  67.     /orgfreq FMLOCAL
  68.     /yscale FMLOCAL
  69.     /xscale FMLOCAL
  70.     /manualfeed FMLOCAL
  71.     /paperheight FMLOCAL
  72.     /paperwidth FMLOCAL
  73. /FMDOCUMENT { 
  74.     array /FMfonts exch def 
  75.     /#copies exch def
  76.     FrameDict begin
  77.     0 ne dup {setmanualfeed} if
  78.     /manualfeed exch def
  79.     /paperheight exch def
  80.     /paperwidth exch def
  81.     setpapername
  82.     manualfeed {true} {papersize} ifelse 
  83.     {manualpapersize} {false} ifelse 
  84.     {desperatepapersize} if
  85.     /yscale exch def
  86.     /xscale exch def
  87.     currenttransfer cvlit /orgxfer exch def
  88.     currentscreen cvlit /orgproc exch def
  89.     /organgle exch def /orgfreq exch def
  90.     end 
  91.     } def 
  92.     /pagesave FMLOCAL
  93.     /orgmatrix FMLOCAL
  94.     /landscape FMLOCAL
  95. /FMBEGINPAGE { 
  96.     FrameDict begin 
  97.     /pagesave save def
  98.     3.86 setmiterlimit
  99.     /landscape exch 0 ne def
  100.     landscape { 
  101.         90 rotate 0 exch neg translate pop 
  102.         }
  103.         {pop pop}
  104.         ifelse
  105.     xscale yscale scale
  106.     /orgmatrix matrix def
  107.     gsave 
  108.     } def 
  109. /FMENDPAGE {
  110.     grestore 
  111.     pagesave restore
  112.     end 
  113.     showpage
  114.     } def 
  115. /FMDEFINEFONT { 
  116.     FrameDict begin
  117.     findfont 
  118.     ReEncode 
  119.     2 index exch 
  120.     definefont exch 
  121.     scalefont 
  122.     FMfonts 3 1 roll 
  123.     put
  124.     end 
  125.     } bind def
  126. /FMNORMALIZEGRAPHICS { 
  127.     newpath
  128.     0.0 0.0 moveto
  129.     1 setlinewidth
  130.     0 setlinecap
  131.     0 0 0 sethsbcolor
  132.     0 setgray 
  133.     } bind def
  134.     /fx FMLOCAL
  135.     /fy FMLOCAL
  136.     /fh FMLOCAL
  137.     /fw FMLOCAL
  138.     /llx FMLOCAL
  139.     /lly FMLOCAL
  140.     /urx FMLOCAL
  141.     /ury FMLOCAL
  142. /FMBEGINEPSF { 
  143.     end 
  144.     /FMEPSF save def 
  145.     /showpage {} def 
  146.     FMNORMALIZEGRAPHICS 
  147.     [/fy /fx /fh /fw /ury /urx /lly /llx] {exch def} forall 
  148.     fx fy translate 
  149.     rotate
  150.     fw urx llx sub div fh ury lly sub div scale 
  151.     llx neg lly neg translate 
  152.     } bind def
  153. /FMENDEPSF {
  154.     FMEPSF restore
  155.     FrameDict begin 
  156.     } bind def
  157. FrameDict begin 
  158. /setmanualfeed {
  159. %%BeginFeature *ManualFeed True
  160.      statusdict /manualfeed true put
  161. %%EndFeature
  162.     } def
  163. /max {2 copy lt {exch} if pop} bind def
  164. /min {2 copy gt {exch} if pop} bind def
  165. /inch {72 mul} def
  166. /pagedimen { 
  167.     paperheight sub abs 16 lt exch 
  168.     paperwidth sub abs 16 lt and
  169.     {/papername exch def} {pop} ifelse
  170.     } def
  171.     /papersizedict FMLOCAL
  172. /setpapername { 
  173.     /papersizedict 14 dict def 
  174.     papersizedict begin
  175.     /papername /unknown def 
  176.         /Letter 8.5 inch 11.0 inch pagedimen
  177.         /LetterSmall 7.68 inch 10.16 inch pagedimen
  178.         /Tabloid 11.0 inch 17.0 inch pagedimen
  179.         /Ledger 17.0 inch 11.0 inch pagedimen
  180.         /Legal 8.5 inch 14.0 inch pagedimen
  181.         /Statement 5.5 inch 8.5 inch pagedimen
  182.         /Executive 7.5 inch 10.0 inch pagedimen
  183.         /A3 11.69 inch 16.5 inch pagedimen
  184.         /A4 8.26 inch 11.69 inch pagedimen
  185.         /A4Small 7.47 inch 10.85 inch pagedimen
  186.         /B4 10.125 inch 14.33 inch pagedimen
  187.         /B5 7.16 inch 10.125 inch pagedimen
  188.     end
  189.     } def
  190. /papersize {
  191.     papersizedict begin
  192.         /Letter {lettertray} def
  193.         /LetterSmall {lettertray lettersmall} def
  194.         /Tabloid {11x17tray} def
  195.         /Ledger {ledgertray} def
  196.         /Legal {legaltray} def
  197.         /Statement {statementtray} def
  198.         /Executive {executivetray} def
  199.         /A3 {a3tray} def
  200.         /A4 {a4tray} def
  201.         /A4Small {a4tray a4small} def
  202.         /B4 {b4tray} def
  203.         /B5 {b5tray} def
  204.         /unknown {unknown} def
  205.     papersizedict dup papername known {papername} {/unknown} ifelse get
  206.     end
  207.     /FMdicttop countdictstack 1 add def
  208.     statusdict begin stopped end 
  209.     countdictstack -1 FMdicttop {pop end} for
  210.     } def
  211. /manualpapersize {
  212.     papersizedict begin
  213.         /Letter {letter} def
  214.         /LetterSmall {lettersmall} def
  215.         /Tabloid {11x17} def
  216.         /Ledger {ledger} def
  217.         /Legal {legal} def
  218.         /Statement {statement} def
  219.         /Executive {executive} def
  220.         /A3 {a3} def
  221.         /A4 {a4} def
  222.         /A4Small {a4small} def
  223.         /B4 {b4} def
  224.         /B5 {b5} def
  225.         /unknown {unknown} def
  226.     papersizedict dup papername known {papername} {/unknown} ifelse get
  227.     end
  228.     stopped 
  229.     } def
  230. /desperatepapersize {
  231.     statusdict /setpageparams known
  232.         {
  233.         paperwidth paperheight 0 1 
  234.         statusdict begin
  235.         {setpageparams} stopped pop 
  236.         end
  237.         } if
  238.     } def
  239. /savematrix {
  240.     orgmatrix currentmatrix pop
  241.     } bind def
  242. /restorematrix {
  243.     orgmatrix setmatrix
  244.     } bind def
  245. /dmatrix matrix def
  246. /dpi    72 0 dmatrix defaultmatrix dtransform
  247.     dup mul exch   dup mul add   sqrt def
  248. /freq dpi 18.75 div 8 div round dup 0 eq {pop 1} if 8 mul dpi exch div def
  249. /sangle 1 0 dmatrix defaultmatrix dtransform exch atan def
  250. /DiacriticEncoding [
  251. /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
  252. /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
  253. /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
  254. /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
  255. /.notdef /.notdef /.notdef /.notdef /space /exclam /quotedbl
  256. /numbersign /dollar /percent /ampersand /quotesingle /parenleft
  257. /parenright /asterisk /plus /comma /hyphen /period /slash /zero /one
  258. /two /three /four /five /six /seven /eight /nine /colon /semicolon
  259. /less /equal /greater /question /at /A /B /C /D /E /F /G /H /I /J /K
  260. /L /M /N /O /P /Q /R /S /T /U /V /W /X /Y /Z /bracketleft /backslash
  261. /bracketright /asciicircum /underscore /grave /a /b /c /d /e /f /g /h
  262. /i /j /k /l /m /n /o /p /q /r /s /t /u /v /w /x /y /z /braceleft /bar
  263. /braceright /asciitilde /.notdef /Adieresis /Aring /Ccedilla /Eacute
  264. /Ntilde /Odieresis /Udieresis /aacute /agrave /acircumflex /adieresis
  265. /atilde /aring /ccedilla /eacute /egrave /ecircumflex /edieresis
  266. /iacute /igrave /icircumflex /idieresis /ntilde /oacute /ograve
  267. /ocircumflex /odieresis /otilde /uacute /ugrave /ucircumflex
  268. /udieresis /dagger /.notdef /cent /sterling /section /bullet
  269. /paragraph /germandbls /registered /copyright /trademark /acute
  270. /dieresis /.notdef /AE /Oslash /.notdef /.notdef /.notdef /.notdef
  271. /yen /.notdef /.notdef /.notdef /.notdef /.notdef /.notdef
  272. /ordfeminine /ordmasculine /.notdef /ae /oslash /questiondown
  273. /exclamdown /logicalnot /.notdef /florin /.notdef /.notdef
  274. /guillemotleft /guillemotright /ellipsis /.notdef /Agrave /Atilde
  275. /Otilde /OE /oe /endash /emdash /quotedblleft /quotedblright
  276. /quoteleft /quoteright /.notdef /.notdef /ydieresis /Ydieresis
  277. /fraction /currency /guilsinglleft /guilsinglright /fi /fl /daggerdbl
  278. /periodcentered /quotesinglbase /quotedblbase /perthousand
  279. /Acircumflex /Ecircumflex /Aacute /Edieresis /Egrave /Iacute
  280. /Icircumflex /Idieresis /Igrave /Oacute /Ocircumflex /.notdef /Ograve
  281. /Uacute /Ucircumflex /Ugrave /dotlessi /circumflex /tilde /macron
  282. /breve /dotaccent /ring /cedilla /hungarumlaut /ogonek /caron
  283. ] def
  284. /ReEncode { 
  285.     dup 
  286.     length 
  287.     dict begin 
  288.     {
  289.     1 index /FID ne 
  290.         {def} 
  291.         {pop pop} ifelse 
  292.     } forall
  293.     Encoding StandardEncoding eq 
  294.     {
  295.         /Encoding DiacriticEncoding def
  296.     }if
  297.     currentdict 
  298.     end 
  299.     } bind def
  300. /graymode true def
  301.     /bwidth FMLOCAL
  302.     /bpside FMLOCAL
  303.     /bstring FMLOCAL
  304.     /onbits FMLOCAL
  305.     /offbits FMLOCAL
  306.     /xindex FMLOCAL
  307.     /yindex FMLOCAL
  308.     /x FMLOCAL
  309.     /y FMLOCAL
  310. /setpatt676 P
  311. 0 F
  312. -0.08 (T) 183.69 676 P
  313. -0.08 (o support routers having insuf) 190.18 676 P
  314. -0.08 (\336cient memory) 333.53 676 P
  315. -0.08 (, areas can be con\336gured as ) 405.63 676 P
  316. (stubs. External LSAs \050often making up the bulk of the Autonomous System\051 are not \337ooded ) 85.54 662 T
  317. (into/throughout stub areas. Routing to external destinations in stub areas is based solely on ) 85.54 648 T
  318. (default.) 85.54 634 T
  319. FMENDPAGE
  320. %%EndPage: "6" 7
  321. %%Page: "7" 7
  322. 612 792 0 FMBEGINPAGE
  323. 72 702 540 720 R
  324. 7 X
  325. 0 K
  326. V
  327. 0 F
  328. 0 X
  329. (RFC 1245) 72 712 T
  330. (OSPF protocol analysis) 249.36 712 T
  331. (July 1991) 493.02 712 T
  332. 72 69.05 540 81 R
  333. 7 X
  334. V
  335. 0 X
  336. ([Moy]) 72 73 T
  337. ([Page 7]) 499.7 73 T
  338. 72 108 540 684 R
  339. 7 X
  340. V
  341. 2 F
  342. 0 X
  343. (3.0  Cost of the pr) 72 673.33 T
  344. (otocol) 193.4 673.33 T
  345. 0 F
  346. -0.1 (This section attempts to analyze how the OSPF protocol will perform and scale in the Internet. In ) 72 646 P
  347. (this analysis, we will concentrate on the following four areas:) 72 632 T
  348. (\245) 72 612 T
  349. 4 F
  350. (Link bandwidth) 85.54 612 T
  351. 0 F
  352. (. In OSPF) 168.53 612 T
  353. (, a reliable \337ooding mechanism is used to ensure that router link ) 215.22 612 T
  354. (state databases are remained synchronized. Individual components of the link state databases ) 85.54 598 T
  355. -0.17 (\050the LSAs\051 are refreshed infrequently \050every 30 minutes\051, at least in the absence of topological ) 85.54 584 P
  356. (changes. Still, as the size of the database increases, the amount of link bandwidth used by the ) 85.54 570 T
  357. (\337ooding procedure also increases.) 85.54 556 T
  358. (\245) 72 536 T
  359. 4 F
  360. -0.03 (Router memory) 85.54 536 P
  361. 0 F
  362. -0.03 (. The size of an OSPF link state database can get quite lar) 166.32 536 P
  363. -0.03 (ge, especially in the ) 441.86 536 P
  364. (presence of many external LSAs. This imposes requirements on the amount of router memory ) 85.54 522 T
  365. (available.) 85.54 508 T
  366. (\245) 72 488 T
  367. 4 F
  368. (CPU usage) 85.54 488 T
  369. 0 F
  370. (. In OSPF) 141.83 488 T
  371. (, this is dominated by the length of time it takes to run the shortest path ) 188.52 488 T
  372. (calculation \050Dijkstra procedure\051. This is a function of the number of routers in the OSPF sys-) 85.54 474 T
  373. (tem.) 85.54 460 T
  374. (\245) 72 440 T
  375. 4 F
  376. (Role of the Designated Router) 85.54 440 T
  377. (.) 238.32 440 T
  378. 0 F
  379. ( The Designated router receives and sends more packets on a ) 241.32 440 T
  380. -0.46 (multi-access networks than the other routers connected to the network. Also, there is some time ) 85.54 426 P
  381. (involved in cutting over to a new Designated Router after the old one fails \050especially when ) 85.54 412 T
  382. (both the Backup Designated Router and the Designated Router fail at the same time\051. For this ) 85.54 398 T
  383. -0.27 (reason, it is possible that you may want to limit the number of routers connected to a single net-) 85.54 384 P
  384. (work.) 85.54 370 T
  385. (The remaining section will analyze these areas, estimating how much resources the OSPF proto-) 72 344 T
  386. -0.05 (col will consume, both now and in the future. T) 72 330 P
  387. -0.05 (o aid in this analysis, the next section will present ) 298.93 330 P
  388. (some data that have been collected in actual OSPF \336eld deployments.) 72 316 T
  389. 3 F
  390. (3.1   Operational data) 72 282.67 T
  391. 0 F
  392. -0.44 (The OSPF protocol has been deployed in a number of places in the Internet. For a summary of this ) 72 256 P
  393. (deployment, see [1]. Some statistics have been gathered from this operational experience, via ) 72 242 T
  394. -0.03 (local network management facilities. Some of these statistics are presented in the following table:) 72 228 P
  395. FMENDPAGE
  396. %%EndPage: "7" 8
  397. 5 10 /Times-Bold FMDEFINEFONT
  398. %%Page: "8" 8
  399. 612 792 0 FMBEGINPAGE
  400. 72 702 540 720 R
  401. 7 X
  402. 0 K
  403. V
  404. 0 F
  405. 0 X
  406. (RFC 1245) 72 712 T
  407. (OSPF protocol analysis) 249.36 712 T
  408. (July 1991) 493.02 712 T
  409. 72 69.05 540 81 R
  410. 7 X
  411. V
  412. 0 X
  413. ([Moy]) 72 73 T
  414. ([Page 8]) 499.7 73 T
  415. 72 108 540 684 R
  416. 7 X
  417. V
  418. 72 666.01 540 674 C
  419. 72 671.98 540 671.98 2 L
  420. 0.5 H
  421. 0 Z
  422. 0 X
  423. 0 K
  424. N
  425. 0 0 612 792 C
  426. 5 F
  427. 0 X
  428. 0 K
  429. (T) 72 677.33 T
  430. (ABLE 1. Pertinent operational statistics) 77.93 677.33 T
  431. (Statistic) 72 655.34 T
  432. (BARRNet) 216 655.34 T
  433. (NSI) 324 655.34 T
  434. (OARnet) 432 655.34 T
  435. 1 F
  436. (Data gathering \050duration\051) 72 638.34 T
  437. (99 hours) 216 638.34 T
  438. (277 hours) 324 638.34 T
  439. (28 hours) 432 638.34 T
  440. (Dijkstra frequency) 72 622.34 T
  441. (50 minutes) 216 622.34 T
  442. (25 minutes) 324 622.34 T
  443. (13 minutes) 432 622.34 T
  444. (External incremental frequency) 72 606.34 T
  445. (1.2 minutes) 216 606.34 T
  446. (.98 minutes) 324 606.34 T
  447. (not gathered) 432 606.34 T
  448. (Database turnover) 72 590.34 T
  449. (29.7 minutes) 216 590.34 T
  450. (30.9 minutes) 324 590.34 T
  451. (28.2 minutes) 432 590.34 T
  452. (LSAs per packet) 72 574.34 T
  453. (3.38) 216 574.34 T
  454. (3.16) 324 574.34 T
  455. (2.99) 432 574.34 T
  456. (Flooding retransmits) 72 558.34 T
  457. (1.3%) 216 558.34 T
  458. (1.4%) 324 558.34 T
  459. (.7%) 432 558.34 T
  460. 0 F
  461. (The \336rst line in the above table show the length of time that statistics were gathered on the three ) 72 533.01 T
  462. (networks. A brief description of the other statistics follows:) 72 519.01 T
  463. (\245) 72 499.01 T
  464. 4 F
  465. (Dijkstra fr) 85.54 499.01 T
  466. (equency) 140.27 499.01 T
  467. (. ) 181.59 499.01 T
  468. 0 F
  469. (In OSPF) 187.59 499.01 T
  470. (, the Dijkstra calculation involves only those routers and transit ) 228.28 499.01 T
  471. -0.14 (networks belonging to the AS. The Dijkstra is run only when something in the system changes ) 85.54 485.01 P
  472. (\050like a serial line between two routers goes down\051. Note that in these operational systems, the ) 85.54 471.01 T
  473. (Dijkstra process runs only infrequently \050the most frequent being every 13 minutes\051.) 85.54 457.01 T
  474. (\245) 72 437.01 T
  475. 4 F
  476. (External incr) 85.54 437.01 T
  477. (emental fr) 153.61 437.01 T
  478. (equency) 206.35 437.01 T
  479. 0 F
  480. (. In OSPF) 247.54 437.01 T
  481. (, when an external route changes only its entry in ) 294.23 437.01 T
  482. -0.13 (the routing table is recalculated. These are called external incremental updates. Note that these ) 85.54 423.01 P
  483. (happen much more frequently than the Dijkstra procedure. \050in other words, incremental ) 85.54 409.01 T
  484. (updates are saving quite a bit of processor time\051.) 85.54 395.01 T
  485. (\245) 72 375.01 T
  486. 4 F
  487. -0.45 (Database turnover) 85.54 375.01 P
  488. -0.45 (.) 179.58 375.01 P
  489. 0 F
  490. -0.45 ( In OSPF) 182.58 375.01 P
  491. -0.45 (, link state advertisements are refreshed at a minimum of every 30 ) 225.36 375.01 P
  492. (minutes. New advertisement instances are sent out more frequently when some part of the ) 85.54 361.01 T
  493. -0.2 (topology changes. The table shows that, even taking topological changes into account, on aver-) 85.54 347.01 P
  494. (age an advertisement is updated close to only every 30 minutes. This statistic will be used in ) 85.54 333.01 T
  495. (the link bandwidth calculations below) 85.54 319.01 T
  496. (. Note that NSI actually shows advertisements updated ) 267.31 319.01 T
  497. (every 30.7 \050> 30\051 minutes. This probably means that at one time earlier in the measurement ) 85.54 305.01 T
  498. (period, NSI had a smaller link state database that it did at the end.) 85.54 291.01 T
  499. (\245) 72 271.01 T
  500. 4 F
  501. -0.39 (LSAs per packet.) 85.54 271.01 P
  502. 0 F
  503. -0.39 ( In OSPF) 173.04 271.01 P
  504. -0.39 (, multiple LSAs can be included in either Link State Update or Link ) 215.95 271.01 P
  505. -0.35 (State Acknowledgment packets.The table shows that, on average, around 3 LSAs are carried in ) 85.54 257.01 P
  506. (a single packet. This statistic is used when calculating the header overhead in the link band-) 85.54 243.01 T
  507. (width calculation below) 85.54 229.01 T
  508. (. This statistic was derived by diving the number of LSAs \337ooded by ) 200.01 229.01 T
  509. (the number of \050non-hello\051 multicasts sent.) 85.54 215.01 T
  510. (\245) 72 195.01 T
  511. 4 F
  512. (Flooding r) 85.54 195.01 T
  513. (etransmits.) 138.97 195.01 T
  514. 0 F
  515. ( This counts both retransmission of LS Update packets and Link State ) 195.92 195.01 T
  516. (Acknowledgment packets, as a percentage of the original multicast \337ooded packets. The table ) 85.54 181.01 T
  517. (shows that \337ooding is working well, and that retransmits can be ignored in the link bandwidth ) 85.54 167.01 T
  518. (calculation below) 85.54 153.01 T
  519. (.) 169.69 153.01 T
  520. FMENDPAGE
  521. %%EndPage: "8" 9
  522. %%Page: "9" 9
  523. 612 792 0 FMBEGINPAGE
  524. 72 702 540 720 R
  525. 7 X
  526. 0 K
  527. V
  528. 0 F
  529. 0 X
  530. (RFC 1245) 72 712 T
  531. (OSPF protocol analysis) 249.36 712 T
  532. (July 1991) 493.02 712 T
  533. 72 69.05 540 81 R
  534. 7 X
  535. V
  536. 0 X
  537. ([Moy]) 72 73 T
  538. ([Page 9]) 499.7 73 T
  539. 72 108 540 684 R
  540. 7 X
  541. V
  542. 3 F
  543. 0 X
  544. (3.2  Link bandwidth) 72 674.67 T
  545. 0 F
  546. -0.02 (In this section we attempt to calculate how much link bandwidth is consumed by the OSPF \337ood-) 72 648 P
  547. (ing process. The amount of link bandwidth consumed increases linearly with the number of ) 72 634 T
  548. (advertisements present in the OSPF database.W) 72 620 T
  549. (e assume that the majority of advertisements in ) 300.88 620 T
  550. (the database will be AS external LSAs \050operationally this is true, see [1]\051.) 72 606 T
  551. (From the statistics presented in Section 3.1, any particular advertisement is \337ooded \050on average\051 ) 72 580 T
  552. (every 30 minutes. In addition, three advertisements \336t in a single packet. \050This packet could be ) 72 566 T
  553. (either a Link State Update packet or a Link State Acknowledgment packet; in this analysis we ) 72 552 T
  554. (select the Link State Update packet, which is the lar) 72 538 T
  555. (ger\051. An AS external LSA is 36 bytes long. ) 320.93 538 T
  556. (Adding one third of a packet header \050IP header plus OSPF Update packet\051 yields 52 bytes. T) 72 524 T
  557. (rans-) 515.59 524 T
  558. (mitting this amount of data every 30 minutes gives an average rate of 23/100 bits/second.) 72 510 T
  559. -0.05 (If you want to limit your routing traf) 72 484 P
  560. -0.05 (\336c to 5% of the link\325) 247.03 484 P
  561. -0.05 (s total bandwidth, you get the following ) 345.75 484 P
  562. (maximums for database size:) 72 470 T
  563. 72 434.01 540 442 C
  564. 72 439.98 540 439.98 2 L
  565. 0.5 H
  566. 0 Z
  567. 0 X
  568. 0 K
  569. N
  570. 0 0 612 792 C
  571. 5 F
  572. 0 X
  573. 0 K
  574. (T) 72 445.33 T
  575. (ABLE 2. Database size as a function of link speed \0505% utilization\051) 77.93 445.33 T
  576. (Speed) 180 423.34 T
  577. (# external advertisements) 288 423.34 T
  578. 1 F
  579. (9.6 Kb) 180 406.34 T
  580. (2087) 288 406.34 T
  581. (56 Kb) 180 390.34 T
  582. (12,174) 288 390.34 T
  583. 0 F
  584. -0.46 (Higher line speeds have not been included, because other factors will then limit database size \050like ) 72 365.01 P
  585. -0.12 (router memory\051 before line speed becomes a factor) 72 351.01 P
  586. -0.12 (. Note that in the above calculation, the size of ) 315.32 351.01 P
  587. -0.06 (the data link header was not taken into account. Also, note that while the OSPF database is likely ) 72 337.01 P
  588. (to be mostly external LSAs, other LSAs have a size also. As a ballpark estimate, router links and ) 72 323.01 T
  589. -0.01 (network links are generally three times as lar) 72 309.01 P
  590. -0.01 (ge as an AS external link, with summary link adver-) 287.18 309.01 P
  591. (tisements being the same size as external link LSAs.) 72 295.01 T
  592. (OSPF consumes considerably less link bandwidth than RIP) 72 269.01 T
  593. (. This has been shown experimentally ) 355.51 269.01 T
  594. (in the NSI network. See Jef) 72 255.01 T
  595. (frey Bur) 203.69 255.01 T
  596. (gan\325) 243.77 255.01 T
  597. (s \322NASA Sciences Internet\323 report in [3].) 264.42 255.01 T
  598. 3 F
  599. (3.3  Router memory) 72 221.67 T
  600. 0 F
  601. -0.1 (Memory requirements in OSPF are dominated by the size of the link state database. As in the pre-) 72 195.01 P
  602. (vious section, it is probably safe to assume that most of the advertisements in the database are ) 72 181.01 T
  603. (external LSAs. While an external LSA is 36 bytes long, it is generally stored by an OSPF imple-) 72 167.01 T
  604. -0.34 (mentation together with some support data. So a good estimate of router memory consumed by an ) 72 153.01 P
  605. (external LSA is probably 64 bytes. So a database having 10,000 external LSAs will consume ) 72 139.01 T
  606. (640K bytes of router memory) 72 125.01 T
  607. (. OSPF de\336nitely requires more memory than RIP) 213.79 125.01 T
  608. (.) 452.98 125.01 T
  609. FMENDPAGE
  610. %%EndPage: "9" 10
  611. %%Page: "10" 10
  612. 612 792 0 FMBEGINPAGE
  613. 72 702 540 720 R
  614. 7 X
  615. 0 K
  616. V
  617. 0 F
  618. 0 X
  619. (RFC 1245) 72 712 T
  620. (OSPF protocol analysis) 249.36 712 T
  621. (July 1991) 493.02 712 T
  622. 72 69.05 540 81 R
  623. 7 X
  624. V
  625. 0 X
  626. ([Moy]) 72 73 T
  627. ([Page 10]) 493.7 73 T
  628. 72 108 540 684 R
  629. 7 X
  630. V
  631. 0 X
  632. -0.35 (Using the Proteon P4200 implementation as an example, the P4200 has 2Mbytes of memory) 72 676 P
  633. -0.35 (. This ) 510.38 676 P
  634. -0.02 (is shared between instruction, data and packet buf) 72 662 P
  635. -0.02 (fer memory) 310.78 662 P
  636. -0.02 (. The P4200 has enough memory to ) 366.26 662 P
  637. (store 10, 000 external LSAs, and still have enough packet buf) 72 648 T
  638. (fer memory available to run a rea-) 367.58 648 T
  639. (sonable number of interfaces.) 72 634 T
  640. (Also, note that while the OSPF database is likely to be mostly external LSAs, other LSAs have a ) 72 608 T
  641. -0.06 (size also. As a ballpark estimate, router links and network links consume generally three times as ) 72 594 P
  642. (much memory as an AS external link, with summary link advertisements being the same size as ) 72 580 T
  643. (external link LSAs.) 72 566 T
  644. 3 F
  645. (3.4  Router CPU) 72 532.67 T
  646. 0 F
  647. (Assume that, as the size of the OSPF routing domain grows, the number of interfaces per router ) 72 506 T
  648. (stays bounded. Then the Dijkstra calculation is of order \050n * log \050n\051\051, where n is the number of ) 72 492 T
  649. (routers in the routing domain. \050This is the complexity of the Dijkstra algorithm in a sparse net-) 72 478 T
  650. (work\051. Of course, it is implementation speci\336c as to how expensive the Dijkstra really is.) 72 464 T
  651. (W) 72 438 T
  652. (e have no experimental numbers for the cost of the Dijkstra calculation in a real OSPF imple-) 82.36 438 T
  653. (mentation. However) 72 424 T
  654. (, Steve Deering presented results for the Dijkstra calculation in the \322MOSPF ) 169.45 424 T
  655. (meeting report\323 in [3]. Steve\325) 72 410 T
  656. (s calculation was done on a DEC 5000 \05010 mips processor\051, using ) 212.9 410 T
  657. (the Stanford internet as a model. His graphs are based on numbers of networks, not number of ) 72 396 T
  658. (routers. However) 72 382 T
  659. (, if we extrapolate that the ratio of routers to networks remains the same, the ) 154.78 382 T
  660. (time to run Dijkstra for 200 routers in Steve\325) 72 368 T
  661. (s implementation was around 15 milliseconds.) 285.87 368 T
  662. -0.46 (This seems a reasonable cost, particularly when you notice that the Dijkstra calculation is run very ) 72 342 P
  663. (infrequently in operational deployments. In the three networks presented in Section 3.1, Dijkstra ) 72 328 T
  664. -0.35 (was run on average only every 13 to 50 minutes. Since the Dijkstra is run so infrequently) 72 314 P
  665. -0.35 (, it seems ) 493.06 314 P
  666. -0.02 (likely that OSPF overall consumes less CPU than RIP \050because of RIP\325) 72 300 P
  667. -0.02 (s frequent updates, requir-) 413.95 300 P
  668. (ing routing table lookups\051.) 72 286 T
  669. (As another example, the routing algorithm in MILNET is SPF-based. MILNET\325) 72 260 T
  670. (s current size is ) 456.42 260 T
  671. -0.02 (230 nodes, and the routing calculation still consumes less than 5% of the MILNET switches\325 pro-) 72 246 P
  672. (cessor bandwidth [4]. Because the routing algorithm in the MILNET adapts to network load, it ) 72 232 T
  673. (runs the Dijkstra process quite frequently \050on the order of seconds as compared to OSPF\325) 72 218 T
  674. (s min-) 499.7 218 T
  675. (utes\051. However) 72 204 T
  676. (, it should be noted that the routing algorithm in MILNET incrementally updates ) 144.79 204 T
  677. (the SPF-tree, while OSPF rebuilds it from scratch at each Dijkstra calculation) 72 190 T
  678. (OSPF\325) 72 164 T
  679. (s Area capability provides a way to reduce Dijkstra overhead, if it becomes a burden. The ) 104 164 T
  680. -0 (routing domain can be split into areas. The extent of the Dijkstra calculation \050and its complexity\051 ) 72 150 P
  681. (is limited to a single area at a time.) 72 136 T
  682. FMENDPAGE
  683. %%EndPage: "10" 11
  684. %%Page: "11" 11
  685. 612 792 0 FMBEGINPAGE
  686. 72 702 540 720 R
  687. 7 X
  688. 0 K
  689. V
  690. 0 F
  691. 0 X
  692. (RFC 1245) 72 712 T
  693. (OSPF protocol analysis) 249.36 712 T
  694. (July 1991) 493.02 712 T
  695. 72 69.05 540 81 R
  696. 7 X
  697. V
  698. 0 X
  699. ([Moy]) 72 73 T
  700. ([Page 11]) 493.7 73 T
  701. 72 108 540 684 R
  702. 7 X
  703. V
  704. 3 F
  705. 0 X
  706. (3.5  Role of Designated Router) 72 674.67 T
  707. 0 F
  708. (This section explores the number of routers that can be attached to a single network. As the num-) 72 648 T
  709. -0.36 (ber of routers attached to a network grows, so does the amount of OSPF routing traf) 72 634 P
  710. -0.36 (\336c seen on the ) 469.48 634 P
  711. (network. Some of this is Hello traf) 72 620 T
  712. (\336c, which is generally multicast by each router every 10 sec-) 238.01 620 T
  713. -0.07 (onds. This burden is borne by all routers attached to the network. However) 72 606 P
  714. -0.07 (, because of its special ) 429.77 606 P
  715. -0.08 (role in the \337ooding process, the Designated router ends up sending more Link State Updates than ) 72 592 P
  716. (the other routers on the network. Also, the Designated Router receives Link State Acknowledg-) 72 578 T
  717. -0.15 (ments from all attached routers, while the other routers just receive them from the DR. \050Although ) 72 564 P
  718. (it is important to note that the rate of Link State Acknowledgments will generally be limited to ) 72 550 T
  719. (one per second from each router) 72 536 T
  720. (, because acknowledgments are generally delayed.\051) 226.38 536 T
  721. -0.22 (So, if the amount of protocol traf) 72 510 P
  722. -0.22 (\336c on the LAN becomes a limiting factor) 228.71 510 P
  723. -0.22 (, the limit is likely to be ) 424.24 510 P
  724. (detected in the Designated Router \336rst. However) 72 496 T
  725. (, such a limit is not expected to be reached in ) 305.68 496 T
  726. (practice. The amount of routing protocol traf) 72 482 T
  727. (\336c generated by OSPF has been shown to be small ) 286.62 482 T
  728. -0.11 (\050see Section 3.2\051. Also, if need be OSPF\325) 72 468 P
  729. -0.11 (s hello timers can be con\336gured to reduce the amount of ) 268.43 468 P
  730. (protocol traf) 72 454 T
  731. (\336c on the network. Note that more than 50 routers have been simulated attached to a ) 131.4 454 T
  732. (single LAN \050see [1]\051. Also, in interoperability testing 13 routers have been attached to a single ) 72 440 T
  733. (ethernet with no problems encountered.) 72 426 T
  734. -0.02 (Another factor in the number of routers attached to a single network is the cutover time when the ) 72 400 P
  735. -0.17 (Designated Router fails. OSPF has a Backup Designated Router so that the cutover does not have ) 72 386 P
  736. -0.31 (to wait for the new DR to synchronize \050the adjacency bring-up process mentioned earlier\051 with all ) 72 372 P
  737. -0.43 (the other routers on the LAN; as a Backup DR it had already synchronized. However) 72 358 P
  738. -0.43 (, in those rare ) 473.46 358 P
  739. -0.33 (cases when both DR and Backup DR crash at the same time, the new DR will have to synchronize ) 72 344 P
  740. (\050via the adjacency bring-up process\051 with all other routers before becoming functional. Field ) 72 330 T
  741. -0.44 (experience show that this synchronization process takes place in a timely fashion \050see the OARnet ) 72 316 P
  742. (report in [1]\051. However) 72 302 T
  743. (, this may be an issue in systems that have many routers attached to a sin-) 183.42 302 T
  744. (gle network.) 72 288 T
  745. -0.15 (In the unlikely event that the number of routers attached to a LAN becomes a problem, either due ) 72 262 P
  746. (to the amount of routing protocol traf) 72 248 T
  747. (\336c or the cutover time, the LAN can be split into separate ) 251 248 T
  748. (pieces \050similar to splitting up the AS into separate areas\051.) 72 234 T
  749. 3 F
  750. (3.6  Summary) 72 200.67 T
  751. 0 F
  752. (In summary) 72 174 T
  753. (, it seems like the most likely limitation to the size of an OSPF system is available ) 128.85 174 T
  754. -0.4 (router memory) 72 160 P
  755. -0.4 (. W) 142.43 160 P
  756. -0.4 (e have given as 10,000 as the number of external LSAs that can be supported by ) 158.39 160 P
  757. (the memory available in one con\336guration of a particular implementation \050the Proteon P4200\051. ) 72 146 T
  758. -0.09 (Other implementations may vary; nowadays routers are being built with more and more memory) 72 132 P
  759. -0.09 (. ) 534.09 132 P
  760. FMENDPAGE
  761. %%EndPage: "11" 12
  762. %%Page: "12" 12
  763. 612 792 0 FMBEGINPAGE
  764. 72 702 540 720 R
  765. 7 X
  766. 0 K
  767. V
  768. 0 F
  769. 0 X
  770. (RFC 1245) 72 712 T
  771. (OSPF protocol analysis) 249.36 712 T
  772. (July 1991) 493.02 712 T
  773. 72 69.05 540 81 R
  774. 7 X
  775. V
  776. 0 X
  777. ([Moy]) 72 73 T
  778. ([Page 12]) 493.7 73 T
  779. 72 108 540 684 R
  780. 7 X
  781. V
  782. 0 X
  783. (Note that 10,000 routes is considerably lar) 72 676 T
  784. (ger than the lar) 275.31 676 T
  785. (gest \336eld implementation \050BARRNet; ) 347.37 676 T
  786. (which at 1816 external LSAs is still very lar) 72 662 T
  787. (ge\051.) 283.65 662 T
  788. (Note that there may be ways to reduce database size in a routing domain. First, the domain can ) 72 636 T
  789. -0.19 (make use of default routing, reducing the number of external routes that need to be imported. Sec-) 72 622 P
  790. (ondly) 72 608 T
  791. (, an EGP can be used that will transport its own information through the AS instead of rely-) 98.54 608 T
  792. -0.21 (ing on the IGP \050OSPF in this case\051 to do transfer the information for it \050the EGP\051. Thirdly) 72 594 P
  793. -0.21 (, routers ) 498.11 594 P
  794. (having insuf) 72 580 T
  795. (\336cient memory may be able to be assigned to stub areas \050whose databases are drasti-) 131.41 580 T
  796. (cally smaller\051. Lastly) 72 566 T
  797. (, if the Internet went away from a \337at address space the amount of external ) 172.82 566 T
  798. (information imported into an OSPF domain could be reduced drastically) 72 552 T
  799. (.) 418.67 552 T
  800. (While not as likely) 72 526 T
  801. (, there could be other issues that would limit the size of an OSPF routing ) 162.17 526 T
  802. (domain. If there are slow lines \050like 9600 baud\051, the size of the database will be limited \050see Sec-) 72 512 T
  803. (tion 3.2\051. Dijkstra may get to be expensive when there are hundreds of routers in the OSPF ) 72 498 T
  804. (domain; although at this point the domain can be split into areas. Finally) 72 484 T
  805. (, when there are many ) 418.69 484 T
  806. (routers attached to a single network, there may be undue burden imposed upon the Designated ) 72 470 T
  807. (Router; although at that point a LAN can be split into separate LANs.) 72 456 T
  808. FMENDPAGE
  809. %%EndPage: "12" 13
  810. %%Page: "13" 13
  811. 612 792 0 FMBEGINPAGE
  812. 72 702 540 720 R
  813. 7 X
  814. 0 K
  815. V
  816. 0 F
  817. 0 X
  818. (RFC 1245) 72 712 T
  819. (OSPF protocol analysis) 249.36 712 T
  820. (July 1991) 493.02 712 T
  821. 72 69.05 540 81 R
  822. 7 X
  823. V
  824. 0 X
  825. ([Moy]) 72 73 T
  826. ([Page 13]) 493.7 73 T
  827. 72 108 540 684 R
  828. 7 X
  829. V
  830. 2 F
  831. 0 X
  832. (4.0  Suitable envir) 72 673.33 T
  833. (onments) 195.21 673.33 T
  834. 0 F
  835. -0.14 (Suitable environments for the OSPF protocol range from lar) 72 646 P
  836. -0.14 (ge to small. OSPF is particular suited ) 359.11 646 P
  837. (for transit Autonomous Systems for the following reasons. OSPF can accommodate a lar) 72 632 T
  838. (ge num-) 497.84 632 T
  839. (ber of external routes. In OSPF the import of external information is very \337exible, having provi-) 72 618 T
  840. -0.39 (sions for a forwarding address, two levels of external metrics, and the ability to tag external routes ) 72 604 P
  841. -0.29 (with their AS number for easy management. Also OSPF\325) 72 590 P
  842. -0.29 (s ability to do partial updates when exter-) 343.17 590 P
  843. (nal information changes is very useful on these networks.) 72 576 T
  844. (OSPF is also suited for smaller) 72 550 T
  845. (, either stand alone or stub Autonomous Systems, because of its ) 220.44 550 T
  846. (wide array of features: fast conver) 72 536 T
  847. (gence, equal-cost-multipath, T) 235.96 536 T
  848. (OS routing, areas, etc.) 382.3 536 T
  849. 2 F
  850. (5.0  Unsuitable envir) 72 469.33 T
  851. (onments) 212.98 469.33 T
  852. 0 F
  853. -0.22 (OSPF has a very limited ability to express policy) 72 442 P
  854. -0.22 (. Basically) 304.62 442 P
  855. -0.22 (, its only policy mechanisms are in the ) 354.25 442 P
  856. (establishment of a four level routing hierarchy: intra-area, inter) 72 428 T
  857. (-area, type 1 and type 2 external ) 374.52 428 T
  858. (routes. A system wanting more sophisticated policies would have to be split up into separate ) 72 414 T
  859. (ASes, running a policy-based EGP between them.) 72 400 T
  860. FMENDPAGE
  861. %%EndPage: "13" 14
  862. %%Page: "14" 14
  863. 612 792 0 FMBEGINPAGE
  864. 72 702 540 720 R
  865. 7 X
  866. 0 K
  867. V
  868. 0 F
  869. 0 X
  870. (RFC 1245) 72 712 T
  871. (OSPF protocol analysis) 249.36 712 T
  872. (July 1991) 493.02 712 T
  873. 72 69.05 540 81 R
  874. 7 X
  875. V
  876. 0 X
  877. ([Moy]) 72 73 T
  878. ([Page 14]) 493.7 73 T
  879. 72 108 540 684 R
  880. 7 X
  881. V
  882. 2 F
  883. 0 X
  884. (6.0  Refer) 72 673.33 T
  885. (ence Documents) 137.87 673.33 T
  886. 0 F
  887. (The following documents have been referenced by this report:) 72 646 T
  888. ([1]) 72 626 T
  889. (Moy) 108 626 T
  890. (, J., \322Experience with the OSPF protocol\323, RFC 1246, July 1991.) 129.88 626 T
  891. ([2]) 72 608 T
  892. (Moy) 108 608 T
  893. (, J., \322OSPF V) 129.88 608 T
  894. (ersion 2\323, RFC 1247, July 1991.) 193.85 608 T
  895. ([3]) 72 590 T
  896. (Corporation for National Research Initiatives, \322Proceedings of the Eighteenth Internet ) 108 590 T
  897. (Engineering T) 108 576 T
  898. (ask Force\323, University of British Columbia, July 30-August 3, 1990.) 176.11 576 T
  899. FMENDPAGE
  900. %%EndPage: "14" 15
  901. %%Page: "15" 15
  902. 612 792 0 FMBEGINPAGE
  903. 72 702 540 720 R
  904. 7 X
  905. 0 K
  906. V
  907. 0 F
  908. 0 X
  909. (RFC 1245) 72 712 T
  910. (OSPF protocol analysis) 249.36 712 T
  911. (July 1991) 493.02 712 T
  912. 72 69.05 540 81 R
  913. 7 X
  914. V
  915. 0 X
  916. ([Moy]) 72 73 T
  917. ([Page 15]) 493.7 73 T
  918. 72 108 540 684 R
  919. 7 X
  920. V
  921. 2 F
  922. 0 X
  923. (Security Considerations) 72 673.33 T
  924. 0 F
  925. (Security issues are not discussed in this memo.) 72 646 T
  926. 2 F
  927. (Author) 72 617.33 T
  928. (\325) 122.04 617.33 T
  929. (s Addr) 126.77 617.33 T
  930. (ess) 173.13 617.33 T
  931. 0 F
  932. (John Moy) 72 590 T
  933. (Proteon Inc.) 72 576 T
  934. (2 T) 72 562 T
  935. (echnology Drive) 87.48 562 T
  936. (W) 72 548 T
  937. (estborough, MA 01581) 82.36 548 T
  938. (Phone: \050508\051 898-2800) 72 522 T
  939. (Email: jmoy@proteon.com) 72 508 T
  940. FMENDPAGE
  941. %%EndPage: "15" 16
  942. %%Trailer
  943. %%BoundingBox: 0 0 612 792
  944. %%Pages: 15 1
  945. %%DocumentFonts: Times-Roman
  946. %%+ Times-Bold
  947.